/**
 * 问题：
 * 链接：
 * 时间复杂度：O();
 * 空间复杂度：O();
 */
//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
class Solution{
    /**
     * 问题：求算术平方根
     * 链接：https://leetcode.cn/problems/sqrtx/
     * 时间复杂度：O(logN);
     * 空间复杂度：O(1);
     */

    //区间划分：mid^2 <= x 求右端点
    public int mySqrt(int x) {
        //1.X < 1
        if( x == 0) return 0;

        long left = 1,right = x;
        //双指针二分查找
        long mid = 0;
        while(left < right){
            mid = left + (right - left + 1) / 2;

            if(mid * mid <= x) left = mid;
            else right = mid - 1;
        }
        return (int)left;
    }

    /**
     * 求插入索引下标
     * https://leetcode.cn/problems/search-insert-position/
     * @param nums
     * @param target
     * @return 下标
     */
    public int searchInsert(int[] nums, int target) {
        int left = 0,right = nums.length - 1;
        while(left < right){

            int mid = left + (right - left) / 2;

            //判断区间 mid < x 区间是合法吗？ 不合法 -》 求左端点
            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }

        //判断是否不在数组范围内
        if(nums[left] < target) return nums.length;
        return left;
    }
}